package zcw.com.lib_leet_code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import zcw.com.lib_leet_code.bean.TreeNode;
import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/7/7.<br><br>
 *
 * 二叉搜索树的最近公共祖先
 */
public class Topic235 {
    public static void main(String[] args) {
        Topic235 instance = new Topic235();

        List<Integer> list = Arrays.asList(6,2,8,0,4,7,9,null,null,3,5);
        TreeNode root = Util.createTree(list);

        TreeNode nodeP = new TreeNode(2);
        TreeNode nodeQ = new TreeNode(8);
        TreeNode result = instance.lowestCommonAncestor(root, nodeP, nodeQ);
        System.out.println(result.val);

        nodeP = new TreeNode(2);
        nodeQ = new TreeNode(4);
        result = instance.lowestCommonAncestor(root, nodeP, nodeQ);
        System.out.println(result.val);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == p || root == q) {
            return root;
        }

        if(root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        else if(root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        else {
            return root;
        }
    }

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> listP = new ArrayList<>();
        List<TreeNode> listQ = new ArrayList<>();
        search(root, p, listP);
        search(root, q, listQ);

        int i = 0;
        int j = 0;
        int lastEqual = -1;
        while (i < listP.size() && j < listQ.size()) {
            if(listP.get(i).val == listQ.get(j).val) {
                lastEqual = i;
                i++;
                j++;
            }
            else {
                break;
            }
        }

        return lastEqual >= 0 ? listP.get(lastEqual) : null;
    }

    private void search(TreeNode root, TreeNode p, List<TreeNode> list) {
        if(root == null) {
            return ;
        }

        list.add(root);
        if(root.val == p.val) {
            return ;
        }

        if(root.val > p.val) {
            search(root.left, p, list);
        }

        if(root.val < p.val) {
            search(root.right, p, list);
        }
    }
}
